package program.leetcode.tree;

/**
 * 307. 区域和检索 - 数组可修改
 *
 * 给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。
 *
 * update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
 *
 * 示例:
 *
 * Given nums = [1, 3, 5]
 *
 * sumRange(0, 2) -> 9
 * update(1, 2)
 * sumRange(0, 2) -> 8
 *
 * 说明:
 *
 *     1. 数组仅可以在 update 函数下进行修改。
 *     2. 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-query-mutable
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode_307 {

    /**
     * sum[i] 存储的是前i个元素的和, sum[0] = 0; sum[1]存储的是nums[0]的数据.
     * sum[i]存储nums[0...i-1]的和. eg: sum[0]=0; sum[1] = nums[0] + sum[0];
     * 因此, 可以得出公式: sum[i] = nums[i - 1] + sum[i - 1].
     */
    private int[] sum;

    /**
     * 保存原始数据.
     */
    private int[] data;

    public LeetCode_307(int[] nums) {
        data = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            data[i] = nums[i];
        }

        // length + 1: 因为sum[0]存储了0.
        sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            sum[i] = nums[i - 1] + sum[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        // sum[j+1]: 存储了0...j的数据之和.
        // sum[i]: 存储了0...i的数据之和.
        return sum[j + 1] - sum[i];
    }

    public void update(int index, int val) {
        data[index] = val;
        // 更新的数据, 只需要更新index之后的数据;
        // 但是, 也是一个O(n)的算法.
        for (int i = index; i < sum.length; i++) {
            sum[i] = sum[i - 1] + data[i - 1];
        }
    }
}


/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */